package ali;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中序遍历：
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
public class Solution_2 {

	//解法1：递归实现
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		inOrder(root, list);
		return list;
	}

	public void inOrder(TreeNode root,List<Integer> list) {
		if (root == null) {
			return;
		}
		inOrder(root.left,list);
		list.add(root.val);
		inOrder(root.right,list);
	}

	//解法2：借助栈，迭代法实现
	public List<Integer> inorderTraversal2(TreeNode root) {
		List<Integer> list = new ArrayList();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack();
		TreeNode curNode = root;
		while (curNode != null || !stack.empty()) { //遍历到底 或者 栈为空
			if (curNode != null) {
				stack.push(curNode); // 入栈
				curNode = curNode.left; // 指向左子节点
			} else {
				curNode = stack.pop(); // 出栈
				list.add(curNode.val); // 保存值
				curNode = curNode.right; // 指向右子节点
			}
		}
		return list;
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

}